import java.util.Iterator;

/**
 * Created with IntelliJ IDEA.
 *
 * @Auther: 邹陆川
 * @Date: 2022/04/19/8:37 上午
 * @Description:使用单链表来实现队列
 */
public class Queue<T> implements Iterable<T>{
  //成员变量
  //头节点
  private Node head;
  //尾节点
  private Node last;
  //队列长度
  private int N;

  @Override
  public Iterator<T> iterator() {
    return new myIterator();
  }
  private class myIterator implements Iterator{
    private Node n;//成员变量
    public myIterator(){
      //初始化
      this.n = head;
    }
    @Override
    public boolean hasNext() {
      return n.next != null;
    }

    @Override
    public Object next() {
      n = n.next;
      return n.item;
    }
  }
  //内部Node类
  private class Node{
    //下一个元素
    private Node next;
    //节点元素值
    private T item;
    //有参构造器
    public Node(Node next, T item) {
      this.next = next;
      this.item = item;
    }
    //无参构造
    public Node() {
    }
  }
  //构造方法


  public Queue() {
    //初始化
    this.head = new Node(null,null);
    this.last = null;
    this.N = 0;
  }
  //是否为空
  public boolean isEmpty(){
    return this.N == 0;
  }
  //获得当前队列元素个数
  public int size(){
    return this.N;
  }
  //往队列插入一个元素
  public void enqueue(T t){
    //获得上一个尾节点
    if(this.last == null){
      //当上一个尾节点为空
      //新建一个节点
      Node newNode = new Node(null,t);
      //让首节点的下一个节点和尾节点都为它
      this.head.next = newNode;
      this.last = newNode;
    }else{
      //得到上一个尾节点
      Node oldLast = this.last;
      //新建一个节点
      Node newNode = new Node(null,t);
      //上一个尾节点指向新节点
      oldLast.next = newNode;
      //将新节点设为队列尾节点
      this.last = newNode;
    }
    //队列长度++
    this.N ++;
  }
  //往队列取出一个元素
  public T dequeue(){
    //获得当前头元素的下一个元素（因为头元素不存值）
    Node oldHead = this.head.next;
    //将头元素指向oldHead的下一个元素
    this.head.next = oldHead.next;
    //元素减一
    this.N --;
    //判断队列是否为空，若为空则要设置last为null
    if(isEmpty()){
      this.last = null;
    }
    return oldHead.item;
  }
}
